//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回 n 皇后不同的解决方案的数量。 
//
// 示例: 
//
// 输入: 4
//输出: 2
//解释: 4 皇后问题存在如下两个不同的解法。
//[
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
// 
//
// 
//
// 提示： 
//
// 
// 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N
//-1 步，可进可退。（引用自 百度百科 - 皇后 ） 
// 
// Related Topics 回溯算法 
// 👍 142 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：N皇后 II
public class P52NQueensIi {

    /**
     *
     * 思路：这道题与51题一模一样，51题存具体结果，这道题只是要计数
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 54.32% 的用户 内存消耗： 36.6 MB , 在所有 Java 提交中击败了 26.48% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int result = 0;

        public int totalNQueens(int n) {
            if(n > 0){
                int[][] datas = new int[n][n];
                dfs(datas, 0, n);
            }
            return result;
        }

        private void dfs(int[][] datas, int j, int n) {
            // j 大于n，代表循环结束，而且前面的都是没有冲突的，所以保存结果
            if (j >= n) {
                result ++;
                return;
            }

            for (int s = 0; s < n; s++) {
                // 检查是否不能放在此处
                if (checkRepeat(datas, j, s)) {
                    continue;
                }
                datas[j][s] = 1;
                dfs(datas, j + 1, n);
                // 不管成功与否，都得回溯
                datas[j][s] = 0;
            }
        }

        // 检查datas[j][k] 之前是否重复
        private boolean checkRepeat(int[][] datas, int j, int k) {
            int tempJ = j;
            int tempK = k;
            // 左斜
            while (j > 0 && k > 0) {
                if (datas[j - 1][k - 1] == 1) {
                    return true;
                }

                j--;
                k--;
            }
            j = tempJ;
            k = tempK;

            // 右斜
            while (j > 0 && k < datas.length - 1) {
                if (datas[j - 1][k + 1] == 1) {
                    return true;
                }
                j--;
                k++;
            }
            j = tempJ;
            k = tempK;

            // 横
            while (k > 0) {
                if (datas[tempJ][k - 1] == 1) {
                    return true;
                }
                k--;
            }
            // 纵
            while (j > 0) {
                if (datas[j - 1][tempK] == 1) {
                    return true;
                }
                j--;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P52NQueensIi().new Solution();
        System.out.println(solution.totalNQueens(4));
        // TO TEST
    }

}